package com.zrrd.zuo.picture;

import java.util.*;

/**
 * @author ywb
 * @Description:
 * @date 2023/4/13 12:49
 */
//拓扑排序
public class TopologySort {
    public static List<Node> SortTopologySort(Graph graph){
        HashMap<Node,Integer> inMap = new HashMap<>();
        Queue<Node> zeroInQueue = new LinkedList<>();
        List<Node> result = new ArrayList<>();
        for(Node node:graph.nodes.values()){
            inMap.put(node,node.in);
            if(node.in == 0){
                zeroInQueue.add(node);
            }
        }
        while (!zeroInQueue.isEmpty()){
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next:cur.nexts){
                inMap.put(next,inMap.get(next)-1);
                if(inMap.get(next)==0){
                    zeroInQueue.add(next);
                }
            }
        }
                return result;
    }
}
